package leetCode.fourthWeek;

public class Code_86 {
  public ListNode partition(ListNode head, int x) {

    if (head == null || head.next == null) {
      return head;
    }

    int i = 0, count_lower = 0, count_higher = 0;
    ListNode res = new ListNode(0);
    ListNode resReturn = res;
    ListNode tmp = head, tmp0 = head;

    while (tmp != null) {
      if (tmp.val < x) {
        res.val = tmp.val;
        if (tmp.next != null | count_lower != i | i == 0) {
          res.next = new ListNode(0);
          res = res.next;
        }
        count_lower++;
      }
      i++;
      tmp = tmp.next;
    }

    while (tmp0 != null) {
      if (tmp0.val >= x) {
        res.val = tmp0.val;
        if (count_higher < i - count_lower - 1) {
          res.next = new ListNode(0);
          res = res.next;
        }
        count_higher++;
      }
      tmp0 = tmp0.next;
    }

    return resReturn;
  }
}
